'''
https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
'''


class Solution:
    def balancedString(self, s: str) -> int:
        idx_map = {'Q': 0, 'W': 1, 'E': 2, 'R': 3}
        times = [0] * 4
        for c in s:
            times[idx_map[c]] += 1
        n = len(s)
        debt = 0
        for i in range(4):
            if times[i] > n // 4:
                times[i] -= n // 4
                debt += times[i]
            else:
                times[i] = 0
        if debt == 0: return 0
        print(times, debt)
        l, r = 0, 0
        ans = len(s)
        while r < n:
            times[idx_map[s[r]]] -= 1
            if times[idx_map[s[r]]] >= 0:
                debt -= 1
            while l <= r and debt == 0:
                ans = min(ans, r - l + 1)
                times[idx_map[s[l]]] += 1
                if times[idx_map[s[l]]] > 0:
                    debt += 1
                l += 1
            r += 1
        return ans

    def balancedString2(self, s: str) -> int:
        cnt_map = {'Q': 0, 'W': 0, 'E': 0, 'R': 0}
        for c in s:
            cnt_map[c] += 1
        n = len(s)
        l, r = 0, 0
        ans = n
        if all(value <= n // 4 for value in cnt_map.values()): return 0
        while r < n:
            cnt_map[s[r]] -= 1
            while l <= r and all(value <= n // 4 for value in cnt_map.values()):
                ans = min(ans, r - l + 1)
                cnt_map[s[l]] += 1
                l += 1
            r += 1
        return ans
